import java.util.Random;
import java.util.Arrays;

public class ReservoirSampler extends QuantileSketch
{
    protected int n = 0;
    protected int k;
    protected double[] s;
    protected Random r;

    public ReservoirSampler(int k)
    {
	this.k = k;
	s = new double[k];
	r = new Random();
    }

    public void insert(double x)
    {
	n += 1;

	if (n <= k)
	    s[n - 1] = x;
	else if (r.nextDouble() * n <= k) // include n-th w.p. k/n
	    s[r.nextInt(k)] = x;          // replace a position at random
    }

    // returns the f-quantile from sample
    public double getQuantile(double f)
    {
	Arrays.sort(s);
	if (f >= 1.0)
	    return s[k - 1];
	else if (f < 0)
	    return s[0];
	else
	    return s[(int)(f * k)];
    }
    

    public double[] getSamples()
    {
	return s;
    }
}